#include <iostream>
#include <vector>
#include <cstdio> 
#include <cstring>
#include <queue>

#define in read()
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef double db;
typedef vector < int >  vec;
typedef pair < int , int > pii;
typedef vector < pii > veg;

int read() {
    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

namespace F { // max_flow
    const int N = 1610;
    const int M = N * 8;
    const ll inf = 0x3f3f3f3f3f3f3f3f;
    int h[N],now[N],d[N],cnt = 1,S,T;
    struct edge { int v;ll w; int nxt; } e[M << 1];
    inline void tlink(int x,int y,ll w) { e[++cnt] = (edge) { y,w,h[x] }; h[x] = cnt; }
    inline void link(int x,int y,ll w) { tlink(x,y,w); tlink(y,x,0); }
    inline void setst(int s,int t) { S = s; T = t; }
    void reset() { cnt = 1; memset(h,0,sizeof h); }
    queue < int > q;
    bool bfs() {
	while(q.size()) q.pop(); q.push(S); memset(d,0,sizeof d); d[S] = 1; now[S] = h[S];
	while(!q.empty()) {
	    int x = q.front(); q.pop();
	    for(int i = h[x],y;i;i = e[i].nxt)
		if(e[i].w && !d[y = e[i].v]) {
		    d[y] = d[x] + 1; q.push(y); now[y] = h[y];
		    if(y == T) return 1;
		}
	} return 0;
    }
    ll dinic(int x,ll flow) {
	if(x == T) return flow;
	ll res = flow;
	for(int i = now[x],y;i && res;i = e[i].nxt) {
	    now[x] = i;
	    if(e[i].w && d[y = e[i].v] == d[x] + 1) {
	       ll k = dinic(y,min(res,e[i].w));
		if(!k) d[y] = 0; e[i].w -= k; e[i ^ 1].w += k; res -= k;
	    }
	}
	return flow - res;
    }
    ll runit() {
	ll maxflow = 0,flow;
	while(bfs()) while(flow = dinic(S,inf)) maxflow += flow;
	return maxflow;
    }
};

const int N = 45;
const int H[] = {1,-1,0,0};
const int L[] = {0,0,1,-1};

int n,m,a[N][N],cnt[2];
ll s[2];

inline int id(int x,int y) { return (x - 1) * m + y; }

bool check(ll x) {
    F :: reset(); ll tot = 0; F :: setst(0,id(n,m) + 1);
    for(int i = 1;i <= n;i++)
	for(int j = 1;j <= m;j++) {
	    if(i + j & 1) {
		F :: link(F :: S,id(i,j),x - a[i][j]); tot += x - a[i][j];
		for(int k = 0;k < 4;k++) {
		    int nx = i + H[k],ny = j + L[k];
		    if(nx > 0 && ny > 0 && nx <= n && ny <= m) {
			F :: link(id(i,j),id(nx,ny),F :: inf);
		    }
		}
	    } else F :: link(id(i,j),F :: T,x - a[i][j]);
	    if(x < a[i][j]) return false;
	}
    return F :: runit() == tot;
}

void solve() {
    n = in,m = in; s[0] = 0; s[1] = 0; cnt[0] = 0; cnt[1] = 0;
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) a[i][j] = in,s[(i + j) & 1] += a[i][j],cnt[(i + j) & 1]++;
    if(cnt[0] != cnt[1]) {
	ll res = (s[0] - s[1]) / (cnt[0] - cnt[1]);
	if(check(res)) printf("%lld\n",(ll) res * cnt[0] - s[0]);
	else puts("-1");
    } else {
	int l = 0,r = 2e9,ans = -1;
	while(l <= r) {
	    int mid = (ll) l + r >> 1;
	    if(check(mid)) ans = mid,r = mid - 1;
	    else l = mid + 1;
	}
	if(ans == -1) puts("-1");
	else printf("%lld\n",(ll) ans * cnt[0] - s[0]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    for(int T = in;T;T--) solve(); return 0;
} 
